/*
 * @lc app=leetcode.cn id=14 lang=cpp
 *
 * [14] 最长公共前缀
 *
 * https://leetcode-cn.com/problems/longest-common-prefix/description/
 *
 * algorithms
 * Easy (32.16%)
 * Total Accepted:    56.5K
 * Total Submissions: 175.4K
 * Testcase Example:  '["flower","flow","flight"]'
 *
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 
 * 如果不存在公共前缀，返回空字符串 ""。
 * 
 * 示例 1:
 * 
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 
 * 
 * 示例 2:
 * 
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * 
 * 
 * 说明:
 * 
 * 所有输入只包含小写字母 a-z 。
 * 
 */
#include <string>
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty())
            return string("");
        string temp = strs.at(0);
        for(int i = 1; i < strs.size(); i++) {
            while(temp != "") {
                size_t res = strs.at(i).find(temp);
                if(res != 0)
                    temp = temp.substr(0, temp.size() - 1);
                else
                {
                    break;
                }
                if(temp == "")
                    return temp;
            }
        }
        return temp;
    }

    //水平扫描法，每一列进行对比
    string longestCommonPrefix_leetcode(vector<string>& strs) {
        if(strs.empty())
            return string("");
        string temp = strs.at(0);
        string result("");
        int j = 0;
        for(j = 0; j < temp.size(); j++) {
            for(int i = 1; i < strs.size(); i++) {
                if(strs[i][j] != temp[j])
                {
                    return result;
                }
            }
            result += temp[j];           
        }
        return result;
    }

    //分治法进行比较，将数组进行分治处理，然后将每一个小的分治的结果进行比较
    string longestCommonPrefix_DC(vector<string>& strs,int l, int r) {
        if(l == r)
            return strs[r];
        int mid = (r + l) / 2;
        string left = longestCommonPrefix_DC(strs, l, mid);
        string right = longestCommonPrefix_DC(strs, mid + 1, r);
        return Compare(left, right);
    }
    string longestCommonPrefix_leetcode_DC(vector<string>& strs) {
        if(strs.empty())
            return string(""); 
        int l = 0;
        int r = strs.size() - 1;
        return longestCommonPrefix_DC(strs, l, r);
    }
    string Compare(string left, string right) {
        if(left == "" || right == "")
            return string("");
        string res("");
        for(int i = 0; i < left.size(); i++) {
            if(left[i] != right[i])
                return res;
            res += left[i];
        }
        return res;
    }
};

int main(int argc, char* argv[]) {
    vector<string> strs = {"flower","flow","flight"};
    vector<string> strs1 = {"caa","","a","acb"};

    Solution sol;
    string re = sol.longestCommonPrefix_leetcode_DC(strs);
    string re1 = sol.longestCommonPrefix_leetcode_DC(strs1);

    cout<<re<<"\n"<<re1<<endl;
    getchar();
    return 0;
}
